/**
 * Created by sunchenglin on 2017/7/17.
 * 归并排序
 //    冒泡排序
 //    选择排序
 //    插入排序
 //    希尔排序
 //    计数排序
 //    桶排序
 //    基数排序
 //    拓扑排序
 //    外部排序
 */
public class Solution {
    public static void change(int i, int j, int[] array){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }


    public static void mergeSort(int[] array, int left, int right){
        if(right-left<1){
            return;
        }
        int mid = (left+right)/2;
        mergeSort(array,left,mid);
        mergeSort(array,mid+1,right);
        merge(array,left,mid,mid+1,right);
    }
    public static void merge(int[] array, int left, int mid, int mid1,int right){
        int[] a = new int[array.length];
        int i=left;
        while(left<=mid&&mid1<=right){
            a[i++] = (array[left]<array[mid1])?array[left++]:array[mid1++];
        }
        if(left<=mid){
            for(int j=left;j<=mid;j++)
                a[i++] = array[j];
        }
        if(mid1<=right){
            for(int j=mid1;j<=right;j++)
                a[i++] = array[j];
        }
        for(int j=left;j<=right;j++)
            array[j] = a[j];
    }
    public static void main(String args[]){
        int[] a={7,4,8,5,3,4,5,2,6};
        mergeSort(a,0,a.length-1);
        System.out.println("haha");
    }
}
